#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        if(n==1){
            return {"()"};
        }
        set<string> S;
        vector<string> sonResult = generateParenthesis(n-1);
        for(int i = 0;i<sonResult.size();++i){
            for(int j = 0;j<sonResult[i].size()+1;++j){
                string temp = "";
                if(j==0){
                    temp += "()"+sonResult[i];
                }
                else{
                    temp = sonResult[i];
                    temp.insert(j-1,"(");
                    temp.insert(j,")");
                }
                if(S.insert(temp).second){
                    result.push_back(temp);
                }
            }
        } 
        return result;
    }
};

int main(){
    Solution S;
    vector<string> result = S.generateParenthesis(3);
    return 0;
}